
\prob{0089}{欠债还钱}

甲欠乙共$x$元，其中$0 < x < 1$。然而，甲只有1元硬币，乙不能找钱。甲决定按如下方式还钱：

第1步：若欠的钱多于0.5元，则硬币换到另一人手中，该人欠对方$1 - x$元，否则不做操作。然后进行第2步。

第2步：拥有硬币的人掷硬币，若掷出正面，则硬币属于掷者，欠的钱相当于还清，停止操作；若掷出反面，则所欠金额加倍，然后进行第1步。

证明：这种还钱方式是公平的，即乙平均来说将从甲得到$x$元。
\problabels{yellow/概率论, green/证明题}

\subsection{二进制}

若每次所欠钱数改变后，亦改变$x$，则步骤可以写成：在第$n - 1$次掷硬币后，若为正面，则拥有硬币的人获得硬币，结束；若为反面，则$x \leftarrow 2x$，若$x > 1/2$，则交换硬币，同时$x \leftarrow 1 - x$。

将$x$写为二进制数，即将其表示为
\[ x = 2^{-1}x_1 + 2^{-2}x_2 + 2^{-3}x_3 + 2^{-4}x_4 + \cdots \]
的形式，其中所有的$x_i$非0即1。

将$x$加倍1次，相当于将$x$的二进制表示左移1位，此时
\[ x \leftarrow 2x = 2^{-1}x_2 + 2^{-2}x_3 + 2^{-3}x_4 + \cdots \]
而且进行此操作时$x \le 1/2$，即$x_1 = 0$，故可省略。继续可以推知，$x$加倍$n - 1$次，其间又交换硬币多次后，
\[ x = 2^{-1}x_n + 2^{-2}x_{n + 1} + 2^{-3}x_{n + 2} + 2^{-4}x_{n + 3} + \cdots \]
此时若$x_n = 1$，则$x > 1/2$。而操作$x \leftarrow 1 - x$可以表示为对于所有的$i$，$x_i \leftarrow 1 - x_i$，这是由于循环$n - 1$次后，
\begin{align*}
  1 - x ={}& \left(2^{-1} + 2^{-2} + 2^{-3} + 2^{-4} + \cdots\right)\cdot1 \\
  &- \left(2^{-1}x_n + 2^{-2}x_{n + 1} + 2^{-3}x_{n + 2} + \cdots\right) \\
  ={}& 2^{-1}(1 - x_n) + 2^{-2}(1 - x_{n + 1}) \\
  &+ 2^{-3}(1 - x_{n + 2})+ 2^{-4}(1 - x_{n + 3}) + \cdots
\end{align*}
记原始的$x_i$为$X_i$。

于是步骤可以写成：在第$n - 1$次掷硬币后，若为正面，则拥有硬币的人获得硬币，结束；若为反面，则将$x$左移1位，若$x_n = 1$，则交换硬币，同时所有的$i$，$x_i \leftarrow 1 - x_i$。

若在第$n$次掷硬币前均掷出反面，考虑第$n - 1$次掷硬币前，硬币的交换次数。若该次数为偶数，则第$n - 1$次掷硬币后，硬币在甲手中，且$x_i = X_i$。于是，只有$X_n = x_n = 1$时，乙才能在第$n$次掷硬币前拥有硬币；

若在第$n$次掷硬币前均掷出反面，且该次数为奇数，则则第$n - 1$次掷硬币后，硬币在乙手中，且$x_i = 1 - X_i$。于是，只有$1 - X_n = x_n = 0$，即$X_n = 1$时，乙才能在第$n$次掷硬币前拥有硬币。

因此，若且唯若$X_n = 1$且已掷出$n - 1$个反面时，乙才能在第$n$次掷硬币前拥有硬币。掷出$n - 1$个反面的概率为$1/\left(2^{n - 1}\right) = 2^{1 - n}$，故乙能在第$n$次掷硬币前拥有硬币的概率为$2^{1 - n}X_n$。而第$n$次掷出正面的概率为$1/2 = 2^{-1}$，故乙恰在掷$n$次硬币后获得1元的概率为$2^nX_n$。考虑所有的$n$，可知乙最终获得1元的概率为
\[ 2^{-1}X_1 + 2^{-2}X_2 + 2^{-3}X_3 + 2^{-4}X_4 + \dots = x \]
同时乙有$1 - x$的概率从甲获得0元，故乙平均可以从甲得到
\[ 1\cdot x + 0\cdot(1 - x) = x \]
元。于是，这种还钱方式是公平的。证毕。
